![]() ![]() ![]() |
Vector
, List
, SingleList
and
Deque
.
It also provides container adaptors that make it easy to construct
abstract data types, such as stacks or queues, out of the basic
sequence kinds (or out of other kinds of sequences that the user might define).
In the following two tables,
X
is a sequence class, a
is value of X
,
i
and j
satisfy input iterator requirements,
[i,j)
is a valid range, n
is a int
,
p
is a valid iterator to a
, q
is a
dereferenceable iterator to a
, [q1,q2)
is a
valid range in a
, t
is a value of
Object
.
The complexities of the expressions are sequence dependent.
The sequence requirements are defined in the SequenceContainer api interface.
expression | return type | assertion/note pre/post-condition |
---|---|---|
X(n, t);
| . |
post: size() == n .constructs a sequence with n copies of t .
|
X(i, j)
| . |
post: size() == distance between i and
j .constructs a sequence equal to the range [i,j) .
|
a.insert(p, t)
|
Iterator
|
inserts a copy of t before p .the return value points to the inserted copy. |
a.insert(p, n, t)
|
void
|
inserts n copies of t before p .
|
a.insert(p, i, j)
|
void
|
inserts copies of elements in [i,j) before p .
|
a.erase(q)
|
void
|
erases the element pointed to by q .
|
a.erase(q1, q2)
|
void
|
erases the elements in the range [q1,q2) .
|
Vector
, List
, and Deque
offer the
programmer different complexity trade-offs and should be used accordingly.
Vector
is the type of sequence that should be used by default.
List
should be used when there are frequent insertions and
deletions from the middle of the sequence.
Deque
is the data structure of choice when most insertions and
deletions take place at the beginning or at the end of the sequence.
Iterator
types for sequences have to be at least of the
forward iterator category.
All the operations in the tables below are provided only for the containers for which they take constant time.
expression | return type | operational semantics | container |
---|---|---|---|
a.front()
|
Object;
|
a.beginRef().get()
|
Vector , List ,Deque
|
a.back()
|
Object;
|
a.end().prev().get()
|
Vector , List ,Deque
|
a.get(n)
|
Object
|
a.begin().next(n).get()
|
Vector , Deque
|
a.put(x, n)
|
Object
|
a.begin().next(n).put(x)
|
Vector , Deque
|
The front insert requirements are defined in the FrontInsertContainer api interface.
expression | return type | operational semantics | container |
---|---|---|---|
a.push_front(t)
|
void
|
a.insert(a.begin(), t)
|
List , Deque
|
a.pop_front()
|
void
|
a.erase(a.begin())
|
List , Deque
|
The back insert requirements are defined in the BackInsertContainer api interface.
expression | return type | operational semantics | container |
---|---|---|---|
a.push_back(t)
|
void
|
a.insert(a.end(), t)
|
Vector , List , Deque
|
a.pop_back()
|
void
|
a.erase(a.endCopy().prev())
|
Vector , List , Deque
|
![]() ![]() ![]() |